
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package Algorithmes;
import Modele.*;
/**
 *
 * @author Kami
 */
public class Cycle {


   private TSPLib_Data graphe;



   public Cycle(TSPLib_Data graphe) {
        this.graphe = graphe;
   }

   public void setGraphe(TSPLib_Data nouveau)
   {
	   this.graphe = nouveau;
   }


   public TSPLib_Data getGraphe()
   {
	   return this.graphe;
   }
   //Fonction qui calcule le meilleur incrémentation du cout du cycle quand on ajoute un sommet au cycle de la
   //solution précédente
   public int Inc(int sommet, Solution solutionPrecedent) {

       int i,j;
       //Chercher le point A du cycle le plus proche du sommet à ajouter

       float distanceMin = Float.MAX_VALUE;
       int A = -1;
       for (i = 0; i < solutionPrecedent.getSolMatrice().length; i++){

               if (solutionPrecedent.getSolMatrice()[i][i] == 1){ // point i est dans le cycle
                   if (graphe.getDistance(sommet, i) < distanceMin){
                       distanceMin = graphe.getDistance(sommet, i);
                       A = i;
                   }
               }
       }


       //Chercher 2 points B,C qui forme des arcs du cycle (BA,CA) avec le point A du cycle
       int B = -1;
       int C = -1;

        for (i = 0; i < solutionPrecedent.getSolMatrice().length; i++){
            if (solutionPrecedent.getSolMatrice()[A][i] == 1 && A!=i && B == -1) { // point i forme un arc du cycle avec point A
                B = i;
            }
            else if (solutionPrecedent.getSolMatrice()[A][i] == 1 && A!=i && B != -1) { // point i forme un arc du cycle avec point A
                C = i;
            }
        }


       //faire un clone de la solution pour faire des modifications dessus
       int resultat = 0;
       //Traiter 3 cas : (A est le point du cycle le plus proche au sommet à ajouter)

       solutionPrecedent.getSolMatrice()[sommet][sommet] = 1;

       // Cas 1 : Cycle n'a qu'un seul sommet A, on relie sommet <-> A
       if (B==-1 && C==-1){
           solutionPrecedent.getSolMatrice()[sommet][A] = 1;
           solutionPrecedent.getSolMatrice()[A][sommet] = 1;

           resultat = graphe.getCycleDistance(A, sommet);



       }

       // Cas 2 : Cycle n'a qu'2 sommet A et B, on relie A-Sommet-B
       else if (B!=-1 && C==-1){
           solutionPrecedent.getSolMatrice()[sommet][A] = 1;
           solutionPrecedent.getSolMatrice()[A][sommet] = 1;
           solutionPrecedent.getSolMatrice()[sommet][B] = 1;
           solutionPrecedent.getSolMatrice()[B][sommet] = 1;

           resultat = graphe.getCycleDistance(A, sommet) + graphe.getCycleDistance(sommet, B) - graphe.getCycleDistance(A,B);

       }

       // Cas 3 : Cycle a au moins 3 points A,B,C avec 2 arcs du cycle BA, AC
       // On compare les 2 possibilités A-sommet-B et A-sommet-C et prendre le meilleur (l'incrémentation minimale)
       else{
           int supprimerAB,supprimerAC;
           supprimerAB = graphe.getCycleDistance(A, sommet) + graphe.getCycleDistance(sommet, B) - graphe.getCycleDistance(A,B);
           supprimerAC = graphe.getCycleDistance(A, sommet) + graphe.getCycleDistance(sommet, C) - graphe.getCycleDistance(A,C);

           if (supprimerAB <= supprimerAC){ // Si supprimer AB donne un cout plus petit que supprimer AC

               solutionPrecedent.getSolMatrice()[sommet][A] = 1;
               solutionPrecedent.getSolMatrice()[A][sommet] = 1;
               solutionPrecedent.getSolMatrice()[sommet][B] = 1;
               solutionPrecedent.getSolMatrice()[B][sommet] = 1;
               solutionPrecedent.getSolMatrice()[A][B] = 0;
               solutionPrecedent.getSolMatrice()[B][A] = 0;

               resultat = supprimerAB; // Si supprimer AC donne un cout plus petit que supprimer AB

           }else{
               solutionPrecedent.getSolMatrice()[sommet][A] = 1;
               solutionPrecedent.getSolMatrice()[A][sommet] = 1;
               solutionPrecedent.getSolMatrice()[sommet][C] = 1;
               solutionPrecedent.getSolMatrice()[C][sommet] = 1;
               solutionPrecedent.getSolMatrice()[A][C] = 0;
               solutionPrecedent.getSolMatrice()[C][A] = 0;

               resultat = supprimerAC;
           }

       }
       return resultat;
   }


   //Fonction qui calcule la décrémentaion du cout d'assignement quand on ajoute un sommet au cycle de la
   //solution précédente
   public int Dec(int sommet, Solution solution) {

        int i, j;
        int resultat =0;

        /*
         * Algorithme générale : parcourir le graphe, pour chaque paire de sommet i,j dans le graphe
         * si i est assigné à j
         * et si cout d'assignement (i,sommet) < cout d'assignement (i,j)
         * on assigne i au sommet et on efface l'arc (i,j)
         */
        for (i = 0; i < solution.getSolMatrice().length; i++) {
            for (j = 0; j < solution.getSolMatrice().length; j++) {

              /*  si i est assigné à j et si cout d'assignement (i,sommet) < cout d'assignement (i,j)*/
                if ((solution.getSolMatrice()[i][j] == 2) && (graphe.getCoutAssignement(i, sommet)) < graphe.getCoutAssignement(i, j)) {

                    // On efface l'arc entre i, j
                    solution.getSolMatrice()[i][j] = 0;
                    solution.getSolMatrice()[j][i] = 0;

                    // on assigne i au sommet
                    solution.getSolMatrice()[i][sommet] = 2;
                    solution.getSolMatrice()[sommet][i] = -2;

                    // On calcule la décrémentaion du cout d'assignement
                    resultat = resultat - graphe.getCoutAssignement(i, sommet) + graphe.getCoutAssignement(i, j);
                }
            }
        }
        return resultat;
   }

   //Fonction floa qui calcule la valeur de L(i,lamda)
   public double L_i_Lamda(double lamda, int inc, int dec){
        return lamda*inc+(1-lamda)*(-dec);
   }

   //Fonction qui calcule le meilleur La






}
